home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / bitmanip.cq / bitmanip.c
C/C++ Source or Header  |  1985-02-06  |  7KB  |  174 lines
  1. /* Some useful bit manipulation functions inspired by the article
  2.  * "Binary Magic Numbers" by Edwin E. Freed in DDJ #78, April 1983.
  3.  *   by Dale Wilson, 1983
  4.  *   placed in the Public Domain
  5.  *   
  6.  * These functions were written so they may be directly translated
  7.  * into assembly language for most computers.
  8.  *
  9.  * These functions were tested on a Zenith 100 computer using the 
  10.  * C86 compiler from Computer Innovations, Inc.
  11.  */
  12. #include <stdio.h>
  13.  
  14.  
  15. #define TRUE 1/* stranger than fiction */
  16. #define FALSE 0 /* fiction */
  17. #define CNTLZ 26 /* MS-DOS eof */
  18.  
  19. #define N 16   /* bits per "word" */
  20. #define V 4    /* log 2 of N */
  21.  
  22. /* Since C does not have binary constants, the binary magic numbers are
  23.  * expressed below in hexadecimal.  B from Freed's article is divided
  24.  * into b1 and b2 since there was no good reason to have them in the
  25.  * same array.
  26.  */
  27. unsigned int b1[V] = { 0x5555, 0x3333, 0x0F0F, 0x00FF };
  28. unsigned int b2[V] = { 0xAAAA, 0xCCCC, 0xF0F0, 0xFF00 };
  29. /* converting binary numbers to Gray code is so simple that it may
  30.  * be best defined as a macro rather than a function.
  31.  */
  32.  
  33. #define binary_to_Gray(x) (x ^ x >> 1) /* X exclusive_or X shifted_right 1 */
  34.  
  35. /* MAIN routine to test the functions.
  36.  *  Numbers (entered in hexadecimal) will be used as arguments in each
  37.  *  of the functions.  As an additional check, the binary number resulting
  38.  *  from the Gray_to_binary function will be converted back to Gray code--
  39.  *  which should result in the original number.
  40.  */
  41.  
  42. main(argc,argv)       int argc; char *argv[];
  43. {      unsigned int r,i;
  44.        int c;
  45.        while(TRUE)                           /* loop forever */
  46.        {
  47.                printf("Enter number: ");
  48.                fscanf(stdin,"%x",&i);        /* read a hexadecimal */
  49.                while((c=getchar()) != '\n')  /* discard rest of line */
  50.                        if(c == EOF || c == CNTLZ) /* except on end of file */
  51.                                exit();         /*   quit */
  52.  
  53.               printf("low clear bit: %d\n", low_clear_bit(i));
  54.               printf("high set bit : %d\n", hi_set_bit(i));
  55.               printf("side sum     : %d\n", side_sum(i));
  56.               printf("parity       : %d\n", parity (i));
  57.               r = Gray_to_binary(i);
  58.               printf("Gray code    : 0x%04x\n", r);
  59.               printf("GTB to Binary: 0x%04x\n", binary_to_Gray(r));
  60.               printf("Reversed bits: 0x%04x\n", reverse_bits(i));
  61.               putchar('\n');                  /* leave a blank line between */
  62.         }
  63. }
  64.  
  65.  
  66. /* This function returns the bit number of the lowest bit in the word
  67.  * which is clear (zero).  The least significant bit is numbered 0, the 
  68.  * bit to the left of that, 1, and so on...
  69.  * A minus 1 is returned for words in which all bits are on.
  70.  * The time to execute this function is proportional to V which is
  71.  * log2 of the number of bits in a word.
  72.  * Note that the function low_set_bit may be created by complementing the
  73.  * argument and calling low_clear_bit.
  74.  */                                                                             
  75. low_clear_bit(value)   unsigned int value;
  76. {      unsigned int temp;
  77.        int i, result;
  78.        if((value = ~value) == 0)                 /* complement, test for zero */
  79.                result = -1;                      /*  zero means no clear bits */
  80.        else
  81.        {       result = 0;
  82.                for (i = V-1; i >= 0; i--)
  83.                {        result <<= 1;            /* make space for next bit */
  84.                         temp = value & b1[i];    /* test using magic numbers */
  85.                         if(temp == 0)
  86.                                 result |= 1;     /* next bit of result is 1 */
  87.                         else
  88.                                 value = temp;    /* discard disqualified bits */
  89.               }
  90.       }
  91.               return(result);
  92. }
  93.  
  94. /* This function returns the bit number of the highest bit in the word
  95.  * which is set (one).  The least significant bit is numbered 0, the
  96.  * bit to the left of that, 1, and so on...
  97.  * A minus 1 is returned for words in which all bits are off.
  98.  * The time to execute this function is proportional to V which is
  99.  * log2 of the number of bits in a word.
  100.  * Note that the function high_clear_bit may be created by complementing the
  101.  * argument and calling high_set_bit.
  102.  */
  103. hi_set_bit(value)      unsigned int value;
  104. {      unsigned int temp;
  105.        int result, i;
  106.        if(value == 0)                            /* if no bits are on */
  107.                result  = -1;                     /*  return that info */
  108.        else
  109.        {       result = 0;
  110.                for(i = V-1; i >= 0; i--)
  111.                {       result <<= 1;             /* space for next bit */
  112.                        temp = value & b2[i];                              
  113.                        if (temp != 0)
  114.                        {        result |= 1;     /* next bit is one */
  115.                                 value = temp;    /* discarded unneeded bits */
  116.                        }
  117.               }
  118.       }
  119.       return(result);
  120. }
  121.  
  122.  
  123. /* This function returns a count of the number of bits which are on in a
  124.  * word.  It executes in a time proportional to V, the log base 2 of the 
  125.  * number of bits in a word.
  126.  * Note that a count of the number of zero bits in the word may be found
  127.  * by complementing the value and calling side_sum.
  128.  */
  129. side_sum(value)        unsigned int value;
  130. {     int i;
  131.       unsigned int s;
  132.       s = 1;
  133.       for(i=0; i<V; i++)       /* use magic in reverse order */
  134.       {
  135.               value = (value & b1[i]) + ((value >> s) & b1[i]);
  136.               s <<= 1;        /* generate the powers of two on the fly */
  137.       }
  138.       return(value);
  139. }
  140. /* This function converts a number expressed in Gray code to the
  141.  * equivalent binary number.  It executes in time proportional to the 
  142.  * log base 2 of the number of bits in the word.
  143.  */
  144.  
  145. Gray_to_binary(value) unsigned int value;
  146. {       unsigned int s;
  147.        for(s = N >> 1; s != 0; s >>= 1)  
  148.        {
  149.                value ^= value >> s;
  150.        }
  151.        return(value);
  152. }
  153.  
  154. /* This function returns the parity of a word--that is, it returns a zero
  155.  * if the number of one bits in the word is even, and a one if the number
  156.  * of one bits in the word is odd.  The low order bit of the results of
  157.  * Gray_to_binary and side_sum both have this property, so isolating this
  158.  * bit gives the desired result.  Gray_to_binary was selected since it is 
  159.  * a faster function than side_sum.
  160.  */
  161. parity(value)          unsigned int value;
  162. {
  163.       return(Gray_to_binary(value) & 1);        /* build on previous word */
  164. }
  165.  
  166. /* This function reverses the bits in a word.  Strangely enough, this turns
  167.  * out to be a very useful function to have available.  Note that this function
  168.  * works only on functions with word lengths which are powers of 2.
  169.  */
  170. reverse_bits(value)    unsigned int value;
  171. {      unsigned int s,i;
  172.        s = 1;                  /* s provides the powers of 2 */
  173.        for(i=0; i<V; i++)
  174.